package leetcode_core.leetcode_5;

import java.util.Arrays;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2022年11月22日 14:55
 */
public class MaxValue {
    private int[][] memo;
    //自顶向下推
    private int dp(int[][] grid,int i,int j){
        if(i == 0 && j == 0){
            return grid[i][j];
        }
        if(i<0 || j<0){
            return Integer.MIN_VALUE;
        }
        if(memo[i][j] == -1){
            memo[i][j] = Math.max(dp(grid,i-1,j),dp(grid,i,j-1))+grid[i][j];
        }
        return memo[i][j];
    }

    public int maxValue(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        memo = new int[n][m];
        for(int i =0;i<n;i++){
            Arrays.fill(memo[i],-1);
        }
        int sum = dp(grid,n-1,m-1);
        return sum;
    }
}
